In recent years, mobile wireless communications have become increasingly popular. Today's wireless network architecture is evolving from a circuit-switched, voice-centric architecture towards an IP-based architecture supporting voice, video, and data services. A wireless communication network includes a wireless sector in which a base station communicates with a group of user mobile stations over a shared frequency channel. In this model, the traffic data can be buffered at the transmitter side and sent to the target user based on a scheduling algorithm. The process of determining which user mobile station is allowed to transmit information is referred to as “scheduling”. In a time-division multiplexing access (TDMA) system, for example, each user mobile station may be assigned with a timeslot during which it may communicate with the base station. There are multiple users with different and time-varying channel conditions at any given time. Each user periodically or continually measure channel gain or Carrier-to-Interference (C/I) ratio and reports that as a channel feedback to the transmitter. In some systems, the user mobile station may estimate their achievable data rate and then send that as their requested data rate instead of sending measured C/I. The packet scheduler at the transmitter side takes the channel feedback from all user mobile stations into account in making decisions as to which user to be served.
In a wireless system serving a large number of randomly distributed user mobile stations, the long-term system throughput can be maximized using a scheduling technique that provides priority for the user mobile station with the best channel condition or the highest requested data rate at the time of transmission. This scheduling technique illustrated in FIG. 1 can achieve a performance gain (referred to as a multi-user diversity gain) of 50% to 100%.
As shown in FIG. 1, a base station 10 may provide wireless communications with multiple user mobile stations U1, U2, . . . , Un. The base station 10 may include a radio resource controller 12 that performs radio resource management operations to support multiple user mobile stations sharing a common frequency channel. The radio resource management operations may involve controlling parameters such as transmit power, channel allocation, handover criteria, modulation scheme, error coding scheme, etc. The radio resource controller 12 enables the base station 10 operating in a multi-user environment to utilize the limited radio spectrum resources and radio network infrastructure as efficiently as possible.
The radio resource controller 12 interacts with a scheduler 14 that allocates available bandwidth among user mobile stations in a particular order. For example, FIG. 1 shows a scheduling order of user mobile stations that request the radio resource controller 12 to provide transmission. The base station 10 may have a buffer memory 16 containing a user buffer for each user mobile station U1, U2, . . . , Un. Each user buffer accumulates packets in a data queue to be transmitted to a respective user mobile station. The scheduler selects one or more packets in turn from each user queue, in accord with its scheduling algorithm, and the selected packets are transmitted over the air to the mobile station in the order selected by the scheduler 14.
The user mobile stations may experience different and time-varying channel conditions at any given time. To monitor channel conditions, each user mobile station may periodically measure the channel gain or Carrier-to-Interference (C/I) ratio, and report it to the radio resource controller 12 as a channel feedback. Instead of sending the C/I ratio, the user mobile station may estimate its date rate achievable based on current channel conditions and send it to the radio resource controller 12 as the requested data rate. The scheduler 14 may make a scheduling decision based on bandwidth allocation for user mobile stations and/or based on their channel feedbacks.
To maximize the throughput or the multi-user gain, the scheduler 14 may give priority to the user mobile station with the best channel condition or to the station that requests the highest data rate. This scheduling technique is called the best rate (BR) scheduling. While the BR scheduling maximizes the sector throughput, it does not provide any fairness to user mobile stations with relatively poor channel conditions, since these user mobile stations have to wait for a long time before they are served. For example, the BR scheduling is unfair to user mobile stations located at larger distances from the base station 10.
To maximize the fairness, the round-robin (RR) scheduling technique may be used. The RR scheduling gives an equal number of time slots to each user mobile station in a round-robin fashion, regardless of channel conditions. While this scheduling method provides fairness, the throughput or multi-user diversity gain may be significantly reduced.
To balance the throughput and fairness requirements, a Proportional Fairness (PF) scheduling algorithm is implemented in some cellular networks. This algorithm involves monitoring the average throughput of each user mobile station, and raising the priority of a user mobile station when its traffic is not transmitted for a long time or its average throughput is lower than the average throughput of other stations.
The PF algorithm computes a PF index as a ratio of the user's channel condition to the user's average received data rate. This ratio represents a combination of a channel condition and a queuing time period for each user. For a user mobile station with a good channel condition, the PF index (i.e. priority) may be lower than that for a station with a poor channel condition, if the station with a good channel condition has been receiving data more frequently (i.e. its average received data rate is higher). Conversely, a user mobile station with a poor channel condition may receive higher PF index (or higher priority), if its average received data rate is lower.
For each user mobile station, the PF algorithm computes a ratio of channel gain CIR (i) to the average received data R(i) at the ith time window:
                              I          ⁡                      (            i            )                          =                              CIR            ⁡                          (              i              )                                                          R              _                        ⁡                          (              i              )                                                          (        1        )            
The average received data, R(i), is computed by the weighted moving average: R(i)=(1−w)· R(i−1)+w·R(i)  (2)where R(i) is the received data rate (set to zero for all user mobile stations which are not served in the current ith window). In equation (2), the weight w should be small to smooth out any abrupt temporary fluctuations in the current window. Thus, the PF scheduler keeps track of the weighted moving average of each user's received data rate, computes the ratio of channel gain to the weighted moving average, and uses this normalized ratio as the criterion for the scheduling. The user with the highest I(i) will be served at the ith time window.
While the PF scheduling algorithm has been effective in providing a good compromise between throughput and fairness, this algorithm does not support Quality-of-Service (QoS) control which enables a network provider to assign different priority to different applications, users, or data flows, or to guarantee a certain level of performance to a certain data flow or user. For example, a QoS mechanism may guarantee a required bit rate, delay, jitter, packet dropping probability and/or bit error rate. Quality of service guarantees are important if the network capacity is insufficient, especially for real-time streaming multimedia applications such as voice over Internet Protocol (IP) and IP television, since these applications often require strict end-to-end delay and delay variation (or jitter). QoS control is very important in wireless data networks where the capacity is a limited resource. For example, QoS is a critical component in the third generation (3G) and fourth generation (4G) wireless networks that need to support real-time voice and video applications.
In particular, wireless networks may be required to provide Differentiated Services (DS) for user traffic. For example, Differentiated Services may be used to provide high-level guaranties of low-latency service to critical network traffic, such as voice or video, while providing lower-level best-effort traffic guaranties to non-critical services such as web traffic or file transfer. Also, Differentiated Services may be utilized to provide a higher level of service for premium users.
The PF scheduling algorithm and its variations do not support user-specific or application-specific QoS. This scheduling technique is based only on signal strength and fairness and does not allow wireless network providers to meet QoS or Differentiated Services requirements. For example, a wireless network provider may need to assign higher priorities to premium user mobile stations or stations implementing real-time applications. However, in accordance with the PF scheduling, premium user mobile stations or user mobile stations implementing real-time applications cannot obtain higher priorities. Instead, they may have to wait for service longer than non-premium user mobile stations, for example, if premium user mobile stations are located farther from the base station than non-premium user mobile stations with the same average data rate.
Some known scheduling techniques, such as weighted fair queuing (WFQ) and weighted round robin (WRR)/Deficit Round Robin (DRR) scheduling are specifically designed to provide fairness, differentiated services and QoS by assigning appropriate weights to each user queue. However, these scheduling techniques are not able to provide a multi-user diversity gain. Therefore, they can not increase the system throughput.
Hence, there is a need for a flexible scheduling technique capable of providing QoS control and differentiated services, while maintaining a balance between the system throughput and fairness to users.